package com.adamjwh.pratice.offer;

/**
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 */

public class FindInArrays {

    public boolean Find(int target, int [][] array) {
        int left = 0;
        int middle;
        int sum = 0;    //数组长
        int index = 0;

        for(int i=0; i<array.length; i++) {
            for(int j=0; j<array[i].length; j++) {
                sum ++;
            }
        }

        int arr[] = new int[sum];   //将二维数组转换为一维数组
        int right = sum - 1;

        for(int i=0; i<array.length; i++) {
            for(int j=0; j<array[i].length; j++) {
                arr[index++] = array[i][j];
            }
        }

        java.util.Arrays.sort(arr);     //排序

        //二分查找
        while(left <= right) {
            middle = (left+right)/2;
            if(target < arr[middle]) {
                right = middle - 1;
            } else if(target > arr[middle]) {
                left = middle + 1;
            } else {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int array[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
        boolean result = new FindInArrays().Find(7, array);
        System.out.println(result);
    }

}
